P2824 排序

题目描述

给出一个 $1$ 到 $n$ 的排列，现在对这个排列序列进行 $m$ 次局部排序，排序分为两种：

• 0 l r 表示将区间 $[l,r]$ 的数字升序排序
• 1 l r 表示将区间 $[l,r]$ 的数字降序排序

注意，这里是对下标在区间 $[l,r]$ 内的数排序。
最后询问第 $q$ 位置上的数字。

输入格式

输入数据的第一行为两个整数 $n$ 和 $m$，$n$ 表示序列的长度，$m$ 表示局部排序的次数。

第二行为 $n$ 个整数，表示 $1$ 到 $n$ 的一个排列。

接下来输入 $m$ 行，每一行有三个整数 $\text{op},l,r$，$\text{op}$ 为 $0$ 代表升序排序，$\text{op}$ 为 $1$ 代表降序排序, $l,r$ 表示排序的区间。

最后输入一个整数 $q$，表示排序完之后询问的位置

$n,m\le {10}^5$，$1\le q\le n$

输出格式

输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第 $q$ 位置上的数字。

Sloution

线段树+二分+01 序列排序

C38 线段树+二分 P2824 [HEOI2016/TJOI2016] 排序 - 董晓 - 博客园

由于给出的是排列，具有单调性，每次将序列中大于等于 mid 的数置为 1，否则置为 0，每次将 01 序列排序之后在题目要查询的位置会有一个 0|1 若为 1，则答案是大于等于这个值的，若为 0，则答案是小于这个值的。

注：当区间全为 0 或全为 1 时需要直接进行下一个循环，不然会RE

#define lc u<<1
#define rc u<<1|1
int n, m;int q;
int a[100010], OP[100010], L[100010], R[100010];
struct Tree { //线段树
    ll l, r, sum, tag;
}tr[400010];

void pushup(ll u) { //上传
    tr[u].sum = tr[lc].sum + tr[rc].sum;
}
void pushdown(ll u) { //下传
    if (tr[u].tag == 0 || tr[u].tag == 1) {
        tr[lc].sum = tr[u].tag * (tr[lc].r - tr[lc].l + 1);
        tr[rc].sum = tr[u].tag * (tr[rc].r - tr[rc].l + 1);
        tr[lc].tag = tr[u].tag;
        tr[rc].tag = tr[u].tag;
        tr[u].tag = -1;
    }
}
void build(ll u, ll l, ll r, ll x) { //建树
    tr[u] = {l,r,a[l] >= x,-1};
    if (l == r) return;
    ll m = l + r >> 1;
    build(lc, l, m, x);
    build(rc, m + 1, r, x);
    pushup(u);
}
void change(ll u, ll l, ll r, ll k) { //区修
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].sum = (tr[u].r - tr[u].l + 1) * k;
        tr[u].tag = k;
        return;
    }
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= m) change(lc, l, r, k);
    if (r > m) change(rc, l, r, k);
    pushup(u);
}
ll query(ll u, ll l, ll r) { //区查
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    ll sum = 0;
    if (l <= m) sum += query(lc, l, r);
    if (r > m) sum += query(rc, l, r);
    return sum;
}
bool check(int x) {
    build(1, 1, n, x);
    for (int i = 1;i <= m;i++) {
        int l = L[i], r = R[i];
        int cnt = query(1, l, r);
        if (cnt == 0 || cnt == r - l + 1) {
            continue;
        }
        if (OP[i] == 0) {
            change(1, l, r - cnt, 0);
            change(1, r - cnt + 1, r, 1);
        } else {
            change(1, l, l + cnt - 1, 1);
            change(1, l + cnt, r, 0);
        }
    }
    return query(1, q, q);
}
void solve() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= m;i++) {
        cin >> OP[i] >> L[i] >> R[i];
    }
    cin >> q;
    int l = 0, r = n + 1;
    while (l + 1 < r) {
        int mid = l + r >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    cout << l << '\n';
}

也可

int l = 1, r = n;
while (l <= r) {
	int mid = l + r >> 1;
	if (check(mid)) {
		l = mid + 1;
	} else {
		r = mid - 1;
	}
}
cout << l - 1 << '\n';